/**
 * //请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
 * //
 * //
 * //
 * // 例如:
 * //给定二叉树: [3,9,20,null,null,15,7],
 * //
 * //     3
 * //   / \
 * //  9  20
 * //    /  \
 * //   15   7
 * //
 * //
 * // 返回其层次遍历结果：
 * //
 * // [
 * //  [3],
 * //  [20,9],
 * //  [15,7]
 * //]
 * //
 * //
 * //
 * //
 * // 提示：
 * //
 * //
 * // 节点总数 <= 1000
 * //
 * // Related Topics 树 广度优先搜索 二叉树 👍 153 👎 0
 */

package com.xixi.dataStructure.tree.binaryTree;

import com.xixi.dataStructure.tree.TreeNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class ID_Offer_32_IIICongShangDaoXiaDaYinErChaShuIiiLcof {
    public static void main(String[] args) {
        Solution solution = new ID_Offer_32_IIICongShangDaoXiaDaYinErChaShuIiiLcof().new Solution();
    }


//leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> res = new ArrayList<>();

            if (root == null) return res;

            //采用两队列交替存放的模式；
            List<TreeNode> thisLevel = new LinkedList<>();

            int level = 1;//记录深度，偶数层遍历时需要反转队列
            thisLevel.add(root);//根节点入队
            List<TreeNode> nextLevel;
            while (!thisLevel.isEmpty()) { //用来遍历层数

                nextLevel = new LinkedList<>();//保存下一层
                List<Integer> thisLevelRes = new ArrayList<>();//用于返回结果
                for (TreeNode treeNode : thisLevel) { //用来遍历单层
                    thisLevelRes.add(treeNode.val); //用于返回结果
                    if (treeNode.left != null) nextLevel.add(treeNode.left);
                    if (treeNode.right != null) nextLevel.add(treeNode.right);
                }
                if (level % 2 == 0) { //偶数层返回反着的结果
                    Collections.reverse(thisLevelRes);
                }
                res.add(thisLevelRes); //当前层处理完毕
                level++;//层级增加
                thisLevel = nextLevel;
            }

            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}